package com.xigua._搜索或回溯算法;

import com.xigua.TreeNode;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，
 * 最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 *
 * @date 2022/3/2022:23
 */
public class _剑指Offer68_II_二叉树的最近公共祖先 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode left = new TreeNode(5,new TreeNode(6),new TreeNode(2,new TreeNode(7),null));
        TreeNode p = new TreeNode(4);
        left.right.right = p;
        TreeNode right = new TreeNode(1,new TreeNode(0),new TreeNode(8));
        root.left = left;
        root.right = right;
        lowestCommonAncestor(root,left,p);
    }

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if ((dfs(root.left,p) && dfs(root.right,q)) ||(dfs(root.left,q) && dfs(root.right,p)) ||
             root ==p || root ==q   ) return root;
        if (dfs(root.left,p) && dfs(root.left,q)){
            return lowestCommonAncestor(root.left,p,q);
        }else {
            return lowestCommonAncestor(root.right,p,q);
        }
    }

    static boolean  dfs(TreeNode root, TreeNode p){
        if (root == null) return false;
        if (root == p) return true;
        return dfs(root.left,p) ||dfs(root.right,p);
    }




}
